package com.chunsoft.sort;

import static com.chunsoft.sort.SortUtils.*;

/**
 * Title: MergeSort.java
 * Description: 归并排序
 * Create DateTime: 2023/11/22 21:57
 *
 * @author chunsoft
 */
public class MergeSort {

    /**
     * 递归方法实现
     *
     * @param arr 数组
     */
    public static void mergeSort1(int []arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        process1(arr, 0, arr.length - 1);
    }

    /**
     * 非递归实现
     * @param arr 数组
     */
    public static void mergeSort2(int []arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        int N = arr.length;

        // 当前有序的左组边界
        int mergeSize = 1;

        while(mergeSize < N) {
            int L = 0;
            while(L < N) {
                // L...mid 左组
                int mid = L + mergeSize - 1;

                if (mid >= N) {
                    break;
                }

                int R = Math.min(mid + mergeSize, N - 1);

                merge(arr, L, mid, R);

                L = R + 1;
            }

            if (mergeSize > (N<<1)) {
                break;
            }

            mergeSize <<= 1;
        }

    }

    public static void process1(int []arr, int L, int R) {

        if (L == R) {
            return;
        }

        int mid = L + ((R - L) >> 2);

        process1(arr, L, mid);
        process1(arr, mid+1, R);
        merge(arr, L, mid, R);
    }

    private static void merge(int[] arr, int L, int mid, int R) {
        // 辅助数组
        int [] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;

        while(p1 <= mid && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }

        while (p2 <= R) {
            help[i++] = arr[p2++];
        }

        for (i = 0; i < help.length; i++) {
            arr[L+i] = help[i];
        }
    }

    public static void main(String[] args) {
        int testTime = 5;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            printArray(arr1);
            int[] arr2 = copyArray(arr1);
            mergeSort2(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
            printArray(arr1);
        }
        System.out.println("验证结果：" + succeed);
    }
}
